#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<map>
#include<algorithm>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(nullptr){}
};

class Solution{
    private:
    vector<pair<int, ListNode*>> Map;

    public:
    //out of time
    ListNode* ans1(ListNode* head){
        ListNode* p = head;
        while(p->next != nullptr){
            ListNode* p2 = p->next;
            while(p2 != nullptr){
               if(p2->val < p->val){
                    int temp = p->val;
                    p->val = p2->val;
                    p2->val = temp;
                }
                p2 = p2->next;
            }
            p = p->next;
        }
        return head;
    }

    ListNode* ans2(ListNode* head){
        ListNode* temp = head;
        while(temp != nullptr){
            Map.push_back({temp->val, temp});
            temp = temp->next;
        }
        sort(Map.begin(), Map.end());
        ListNode* ret, *tail;
        for(auto it = Map.begin(); it != Map.end(); it++){
            if(it == Map.begin()){
                ret = tail = it->second;
            }else{
                tail->next = it->second;
                tail = tail->next;
            }
        }
        tail->next = nullptr;

        return ret;
    }

    ListNode* createList(vector<int>& nums){
        ListNode* head = new ListNode(nums[0]);
        ListNode* tail = head;
        for(int i = 1; i != nums.size(); i++){
            ListNode* temp = new ListNode(nums[i]);
            tail->next = temp;
            tail = temp;
        }
        return head;
    }

    void show(ListNode* root){
        ListNode* head = root;
        while(head != nullptr){
            cout << head->val << " " << ends;
            head = head->next;
        }
        cout << endl;
    }
};

void test1(){
    Solution s;
    vector<int> nums = {4,2,1,3};
    ListNode* ret = s.createList(nums);
    ret = s.ans2(ret);
    s.show(ret);
}

void test2(){
    Solution s;
    vector<int> nums = {1,3,3,1,3,1,3,3,2,3,2,2,1,1,1,3,2,2,1,1};
    ListNode* ret = s.createList(nums);
    ret = s.ans2(ret);
    s.show(ret);
}

int main(void){
    test1();
    test2();

    return 0;
}